#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e3+5;
int Tim,T,n,m,ans,pre[N],dis[N];
vector<array<int,2>>G[N];
inline void bfs(int S){
	for(int i=1;i<=n;++i) dis[i]=N;
	queue<int>Q;
	dis[S]=0,Q.push(S);
	while(Q.size()){
		int x=Q.front();Q.pop();
		for(auto to:G[x]){
			int v=to[0];
			if(dis[v]>dis[x]+1) dis[v]=dis[x]+1,Q.push(v),pre[v]=x;
			else if(v!=pre[x]) ans=min(ans,dis[x]+dis[v]+1);
		}
	}
}
int vis[N],res[N],fw[N];
inline void pr(int S){
	for(int i=1;i<=n;++i) dis[i]=N,vis[i]=0;
	queue<int>Q;
	dis[S]=0,Q.push(S),vis[S]=1;
	while(Q.size()){
		int x=Q.front();Q.pop();
		for(auto to:G[x]){
			int v=to[0];
			if(dis[v]>dis[x]+1) dis[v]=dis[x]+1,Q.push(v),pre[v]=x,fw[v]=to[1];
			else if(v!=pre[x]){
				if(dis[x]+dis[v]+1==ans){
					res[to[1]]=1;
					for(int i=x;!vis[i];i=pre[i]) vis[i]=1,res[fw[i]]=1;
					for(int i=v;!vis[i];i=pre[i]) vis[i]=1,res[fw[i]]=1;
				}
			}
		}
	}
}

inline void solve(int id){
	cin>>n>>m,ans=1e9;
	for(int i=1;i<=n;++i) G[i].clear();
	// if(id==9) cerr<<n<<"\n";
	for(int u,v,i=1;i<=m;++i){
		cin>>u>>v,G[u].pb({v,i}),G[v].pb({u,i}),res[i]=0;
		// if(id==9) cerr<<u<<" "<<v<<"\n";
	}
	for(int i=1;i<=n;++i) bfs(i);
	for(int i=1;i<=n;++i) pr(i);
	int cnt=0;
	for(int i=1;i<=m;++i) cnt+=res[i];
	cout<<-(ans-2+m)<<" "<<cnt<<"\n";
}
signed main(){
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>Tim>>T;
	for(int i=1;i<=T;++i) solve(i);
}